//
//  2.替换空格.swift
//  数据结构与算法
//
//  Created by ZERO on 2021/5/17.
//

import Foundation
/*
 题目：请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
 思路：可api实现，也可以遍历替换但是时间复杂度为O(n^2)，下面为O(n)思路
 我们可以先遍历⼀次字符串，这样就可以统计出字符串空格的总数，并可以由此计算出替换之后的字符串的总⻓度。每替换⼀个空格，⻓度增加2，因 替换以后字符串的⻓度等于原来的⻓度加上2乘以空格数⽬。以"We are happy"为例，"We are happy"这个字符串的⻓度为14（包括结尾符号"\n"），⾥⾯有 两个空格，因此替换之后字符串的⻓度是18。 我们从字符串的尾部开始复制和替换。⾸先准备两个指针，P1和P2，P1指向原始字符串的末尾，⽽P2指向替换之后的字符串的末尾。接下来我们向前 移动指针P1，逐个把它指向的字符复制到P2指向的位置，直到碰到第⼀个空格为⽌。碰到第⼀个空格之后，把P1向前移动1格，在P2之前插⼊字符 串"%20"。由于"%20"的⻓度为3，同时也要把P2向前移动3格。
 */
func offer_2() {
    print(replaceSpace(str: "We Are Happy"))
}

fileprivate func replaceSpace(str: String) -> String {
    var str = str
    /*
     // api实现
     str = str.replacingOccurrences(of: " ", with: "%20")
     */
    var spaceCount = 0
    for c in str {
        if c == " " {
            spaceCount += 1
        }
    }
    var i = str.count + spaceCount * 2 - 1
    var j = str.count - 1
    // 扩展字符串空间
    str.append(contentsOf: Array(repeating: " ", count: spaceCount * 2))
    while i >= 0 && j >= 0 {
        if str[j] == " " {
            str[i] = "0"
            str[i-1] = "2"
            str[i-2] = "%"
            i -= 3
        } else {
            str[i] = str[j]
            i -= 1
        }
        j -= 1
        print(str)
    }
    return str
}

fileprivate extension String {
    var length: Int {
        return count
    }
    
    subscript (i: Int) -> String {
        set {
            self[i ..< i + 1] = newValue
        }
        get {
            self[i ..< i + 1]
        }
    }
    
    func substring(fromIndex: Int) -> String {
        return self[min(fromIndex, length) ..< length]
    }
    
    func substring(toIndex: Int) -> String {
        return self[0 ..< max(0, toIndex)]
    }
    
    subscript (r: Range<Int>) -> String {
        set {
            let range = Range(uncheckedBounds: (lower: max(0, min(length, r.lowerBound)),
                                                upper: min(length, max(0, r.upperBound))))
            let start = index(startIndex, offsetBy: range.lowerBound)
            let end = index(start, offsetBy: range.upperBound - range.lowerBound)
            self.replaceSubrange(start ..< end, with: newValue)
        }
        get {
            let range = Range(uncheckedBounds: (lower: max(0, min(length, r.lowerBound)),
                                                upper: min(length, max(0, r.upperBound))))
            let start = index(startIndex, offsetBy: range.lowerBound)
            let end = index(start, offsetBy: range.upperBound - range.lowerBound)
            return String(self[start ..< end])
        }
    }
}
